package algorithm;

import java.util.Arrays;

/**
 *
 * @author: vince_zww
 * @date: 2019/9/5 15:03
 * @desceription:
 * 排序算法1，比较简单的排序算法；
 * 测试运行时间结果根据数据变化而变化，依据平均时间来看，下面的例子只是初略计算而已；冒泡相对低一点点。
 */
public class Sort1 {

    public static void main(String[] args) {
        int c[]={99,9,6,8,10,2,5,3,4,7,12,15,48,78,95,35,23,29,98,19};

        long bubbleSortStartTime = System.nanoTime();
        System.out.println(Arrays.toString(bubbleSort(c,c.length)));
        long bubbleSortEndTime = System.nanoTime();
        System.out.println("冒泡排序运行时间："+(bubbleSortEndTime-bubbleSortStartTime)+"ns");

        long insertionSortStartTime = System.nanoTime();
        System.out.println(Arrays.toString(insertionSort(c,c.length)));
        long insertionSortEndTime = System.nanoTime();
        System.out.println("插入排序运行时间："+(insertionSortEndTime-insertionSortStartTime)+"ns");

        long selectionSortStartTime = System.nanoTime();
        System.out.println(Arrays.toString(selectionSort(c,c.length)));
        long selectionSortEndTime = System.nanoTime();
        System.out.println("选择排序运行时间："+(selectionSortEndTime-selectionSortStartTime)+"ns");

    }

    /**
     * 冒泡排序
     *
     */
    private static int[] bubbleSort(int[] a,int n){
        if(n<=1) {return a;}
        for (int i=0;i<n;i++){
            boolean flag = false;
            for (int j=0;j<n-i-1;++j){
                //交换
                if(a[j]>a[j+1]){
                    int k=a[j];
                    a[j]=a[j+1];
                    a[j+1]=k;
                    flag=true;
                }
            }
            if(!flag){break;}

        }
        return a;
    }

    /**
     * 插入排序
     */
    private static int[] insertionSort(int[] a,int n){
        if(n<=1){return a;}
        for (int i = 1; i < n; i++) {
            int value = a[i];
            int j=i-1;
            //查找插入的位置
            for (;j>=0;--j){
                if(a[j]>a[i]){
                    a[j+1]=a[j];   //位移
                }else {
                    break;
                }
            }
            a[j+1]=value;   //插入
        }
        return a;
    }

    /**
     * 选择排序
     */
    private static int[] selectionSort(int[] a,int n){
        if(n<=1){return a;}
        int i;  //有序区的末尾位置
        int j;  //无序区的起始位置
        int min;    //无序区中最小元素位置

        for (i = 0; i < n; i++) {
            min=i;
            for (j = i+1; j < n; j++) { //找出最小数字的位置
                if(a[j] < a[min]){
                    min=j;
                }
            }
            if(min!=i){ //如果最小数位置变化则交换
                int k=a[i];
                a[i]=a[min];
                a[min]=k;
            }
        }
        return a;
    }
}
